try:
    from commonfuncs.continuedfractionsFrac import cf2fraction
    from commonfuncs.continuedfractionsSQRT import continuedfractionsSQRT
except:
    from continuedfractionsFrac import cf2fraction
    from continuedfractionsSQRT import continuedfractionsSQRT



def solve(D: int) -> tuple:
    '''
    >>> print(solve(5))
    (9, 4)
    >>> print(solve(20))
    (9, 2)
    >>> print(solve(61))
    (1766319049, 226153980)
    '''

    if not isinstance(D, int) or D < 0:
        return False

    D_sqrt = D**0.5
    if int(D_sqrt) == D_sqrt:
        return 1, 0

    cf = continuedfractionsSQRT(D)
    cflist = [cf[0]] + list(cf[1])[:-1]
    p, q = cf2fraction(cflist)
    if len(cf[1]) % 2:
        return 2*p*p+1, 2*p*q
    else:
        return p, q


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

